package com.enums.每个枚举对象单独实现接口;

import java.util.LinkedList;
import java.util.List;

/**
 * <pre>
 * 功能描述：图
 * </pre>
 *
 * @author: 李明杰
 * @date: 2022/6/19 18:08
 */
public class GraphUtil {
    public static void main(String[] args) {
        int[][] a = {
                {0, 1},
                {2, 3}
        };

        List[] graph = GraphEnum.DIRECTED_GRAPH.buildGraph(4, a, 0);
    }


    /**
     * 构建无向图
     *
     * @param n        节点个数
     * @param relation 二维数组给出各个顶点之间的关系
     * @param offset   偏移量（从offset开始为第一个节点）
     * @return 根据二维数组关系构建图的邻接表表示法
     */
    public static List<Integer>[] buildUndirectedGraph(int n, int[][] relation, int offset) {
        // 图节点编号从 n 开始
        n += offset;
        List<Integer>[] graph = new LinkedList[n];
        for (int i = offset; i < n; i++) {
            graph[i] = new LinkedList<>();
        }

        for (int[] edge : relation) {
            int w = edge[1];
            int v = edge[0];
            graph[v].add(w);
            graph[w].add(v);
        }
        return graph;
    }


    /**
     * 构建有向图
     *
     * @param n        节点个数
     * @param relation 二维数组给出各个顶点之间的关系[[from1,to1],[from2,[to2],...]
     * @param offset   偏移量（从offset开始为第一个节点）
     * @return 根据二维数组关系构建图的邻接表表示法
     */
    public static List<Integer>[] buildDirectedGraph(int n, int[][] relation, int offset) {
        // 图节点编号从 n 开始
        n += offset;
        List<Integer>[] graph = new LinkedList[n];
        for (int i = offset; i < n; i++) {
            graph[i] = new LinkedList<>();
        }

        for (int[] edge : relation) {
            int from = edge[0];
            int to = edge[1];
            graph[from].add(to);
        }

        return graph;
    }

    /**
     * 构建有向图
     *
     * @param n        节点个数
     * @param relation 二维数组给出各个顶点之间的关系[[from1,to1,weight1],[from2,to2,weight2],...]
     * @param offset   偏移量（从offset开始为第一个节点）
     * @return 根据二维数组关系构建图的邻接表表示法
     */
    public static List<int[]>[] buildWeightedDirectedGraph(int n, int[][] relation, int offset) {
        // 图节点编号从 n 开始
        n += offset;
        List<int[]>[] graph = new LinkedList[n];
        for (int i = offset; i < n; i++) {
            graph[i] = new LinkedList<>();
        }
        // 构造图
        for (int[] edge : relation) {
            int from = edge[0];
            int to = edge[1];
            int weight = edge[2];
            // 邻接表存储图结构，同时存储权重信息
            graph[from].add(new int[]{to, weight});

        }


        return graph;
    }
}